class BinaryTree{
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

let root = new BinaryTree(1, null, null);
root.left = new BinaryTree(2, null, null);
root.right = new BinaryTree(3, null, null);
root.left.left = new BinaryTree(4, null, null);
root.left.right = new BinaryTree(5, null, null);
root.right.left = new BinaryTree(6, null, null);

const preOrderTraversal = (root) => {
    let result = [];
    if(root == null) return result;
    let stack = [];
    stack.push(root);
    while (stack.length){
        let node = stack.pop();
        result.push(node.value);
        if(node.right) stack.push(node.right);
        if(node.left) stack.push(node.left);
    }
    return result;
}

const minOrderTraversal = (root) => {
    let result = [];
    if(root === null) return result;
    let stack = [];
    let p = root;
    while (stack.length || p){
        while (p){
            stack.push(p);
            p = p.left;
        }
        let node = stack.pop();
        result.push(node.value);
        p = node.right;
    }
    return result;
}

const postOrderTraverse = (root) => {
    let result = [];
    if(root == null) return result;
    let stack = [];
    let visited = new WeakSet();
    let p = root;
    while (stack.length || p){
        while (p){
            stack.push(p);
            p = p.left;
        }
        // 走到这一步p已经是null了
        let node = stack[stack.length - 1];
        if(node.right && !visited.has(node)){
            p = node.right;
            visited.add(node);
        }else{
            result.push(node.value);
            stack.pop();
        }
    }
    return result;
}

const levelOrderTraverse = (root) => {
    let result = [];
    if(root == null) return result;
    let queue = [];
    queue.push(root);
    while (queue.length){
        let size = queue.length;
        while (size--){
            let node = queue.shift();
            result.push(node.value);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return result;
}

const maxTreeHeight = (root) => {
    let level = 0;
    if(root == null) return level;
    let queue = [];
    queue.push(root);
    while (queue.length){
        let size = queue.length;
        while (size--){
            let node = queue.shift();
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        level++;
    }
    return level;
}

const closetParentNode = (root,node1,node2) => {
    if(root == null || node1 == null || node2== null) return null;
    let queue = []; let map = new WeakMap(); let set = new WeakSet;
    let p = node1, q = node2;
    queue.push(root);
    while (queue.length){
        let size = queue.length;
        while (size--){
            let node = queue.shift();
            if(node.left){
                queue.push(node.left);
                map.set(node.left,node);
            }
            if(node.right){
                queue.push(node.right);
                map.set(node.right,node);
            }
        }
    }
    while (p){
        set.add(p);
        p = map.get(p);
    }
    while (q){
        if(set.has(q)){
            return q;
        }else{
            q = map.get(q);
        }
    }
}


// let node1 = root.left;
// let node2 = root.left.left;
// console.log(closetParentNode(root,node1,node2));


